package com.mlh.heap;

import java.util.PriorityQueue;

/**
 * @author 缪林辉
 * @date 2024/9/4 23:44
 * @DESCRIPTION
 */
// 中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
// 例如 arr = [2,3,4] 的中位数是 3 。
// 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
// 实现 MedianFinder 类:
// MedianFinder() 初始化 MedianFinder 对象。
// void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
// double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10^-5 以内的答案将被接受。
public class 数据流的中位数 {
    // 一句话题解：左边大顶堆，右边小顶堆，小的加左边，大的加右边，平衡俩堆数，堆顶给对家，奇数取多的，偶数取除2.
    PriorityQueue<Integer> min;
    PriorityQueue<Integer> max;

    public 数据流的中位数() {
        // 大根堆
        min = new PriorityQueue<>((o1, o2) -> o2 - o1);
        max = new PriorityQueue<>();
    }

    public void addNum(int num) {
        if (min.isEmpty() || num <= min.peek()) {
            min.offer(num);
            if (max.size() + 1 < min.size()) {
                max.offer(min.poll());
            }
        } else {
            max.offer(num);
            if (max.size() > min.size()) {
                min.offer(max.poll());
            }
        }
    }

    public double findMedian() {
        if ((max.size() + min.size()) % 2 == 0) {
            return (max.peek() + min.peek()) / 2.0;
        }
        return min.peek();
    }

    public void addNumPractice(int num) {
        //如果比大根堆的队头大，则进入小根堆
        //如果比大根堆的队头小，则进入大根堆
        if(min.isEmpty()||num<min.peek()){
            min.add(num);
        }else{
            max.add(num);
        }
        //判断两堆大小，多的给少的
        if (min.size() - max.size() > 1) {
            max.add(min.poll());
        } else if (min.size() - max.size() < -1) {
            min.add(max.poll());
        }
    }

    public double findMedianPractice() {
        if((max.size()+min.size())%2==0){//偶数
            return ((double)min.peek()+(double)max.peek())/2;
        }else{//奇数
            return min.size()>max.size()?min.peek():max.peek();
        }
    }
}
